package leetcode;

/**
 * Created by Ghost on 2014/11/3 0003.
 */
public class Word_Search {
    public boolean exist(char[][] board, String word) {
        char begin = word.charAt(0);
        boolean exist = false;
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==begin){
                    board[i][j]='0';
                    exist = search(board,i,j,1,word);
                    if(exist)
                        return exist;
                    board[i][j]=begin;
                }
            }
        }
        return false;
    }

    public boolean search(char[][] board,int line, int row, int cur, String word){
        if(cur==word.length())
            return true;
        char target = word.charAt(cur);
        int i,j;
        boolean exist;
        i=line-1;j=row;
        if(i>=0){
            if(target==board[i][j]){
                board[i][j]='0';
                exist = search(board,i,j,cur+1,word);
                if(exist)
                    return true;
                board[i][j]=target;
            }
        }


        i=line+1;j=row;
        if(i<board.length){
            if(target==board[i][j]){
                board[i][j]='0';
                exist = search(board,i,j,cur+1,word);
                if(exist)
                    return true;
                board[i][j]=target;
            }
        }

        i=line;j=row-1;
        if(j>=0){
            if(target==board[i][j]){
                board[i][j]='0';
                exist = search(board,i,j,cur+1,word);
                if(exist)
                    return true;
                board[i][j]=target;
            }
        }

        i=line;j=row+1;
        if(j<board[0].length){
            if(target==board[i][j]){
                board[i][j]='0';
                exist = search(board,i,j,cur+1,word);
                if(exist)
                    return true;
                board[i][j]=target;
            }
        }

        return false;
    }
    public static void main(String[] args){
        char[][] board = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
        Word_Search word_search = new Word_Search();

        System.out.println(word_search.exist(board,"abcese"));
    }
}
